package com.hanxiaozhang.no10leetcode.dynamicprogramming;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 在一个m * n的方格中，假设一个机器人初始化在左上角的位置，每次只能向下或向右移动一格，
 * 找出移动到右下角的所有路径。 假设在网格中有障碍物存在。
 * 实例1:
 * 输入:
 * [
 * [0,0,0],
 * [0,1,0],
 * [0,0,0]
 * ]
 * 输出: 2
 * 解释:
 * 在上面的3×3网格中间有一个障碍物，有两种方法可以到达右下角
 * Right -> Right -> Down -> Down
 * Down -> Down -> Right -> Right
 *
 * @author hanxinghua
 * @create 2024/3/4
 * @since 1.0.0
 */
public class No63UniquePathsII {

    public static void main(String[] args) {

        int[][] nums = {
                {0, 0, 0},
                {0, 1, 0},
                {0, 0, 0}
        };

        System.out.println(method1(nums));
    }


    private static long method1(int[][] nums) {

        if (nums.length == 0 || nums[0].length == 0) {
            return 0;
        }
        return backTrack(nums, 0, 0);
    }


    private static Long backTrack(int[][] nums, int curI, int curJ) {

        if (curI >= nums[0].length || curJ >= nums.length || nums[curI][curJ] == 1) {
            return 0L;
        }
        if (curI == nums[0].length - 1 && curJ == nums.length - 1) {
            return 1L;
        }
        return backTrack(nums, curI + 1, curJ) +
                backTrack(nums, curI, curJ + 1);
    }


    /**
     * 动态规划
     * <p>
     * pass
     *
     * @return
     */
    private static int method2() {


        return 0;
    }
}
